package suanfa;

public class QuickSort {
	private QuickSort(){}
	
	/*public static void sort(Comparable[] arr,int l,int r){		
				if(l<r){			
			Comparable e=arr[l];
			int low=l;
			int high=r;			
			while(low<high){
				while(low<high && e.compareTo(arr[high])<0)				
					high--;
				if(low<high){
					arr[low]=arr[high];
					low++;
				}
				while(low<high&&e.compareTo(arr[low])>0)
					low++;
				if(l<r){
					arr[high]=arr[low];
					high--;
				}				
			}
			arr[low]=e;
			sort(arr,l,low-1);
			sort(arr,low+1,r);
			}
				}*/
	
	public static int partition(Comparable[] arr,int l,int r){
		
		swap(arr,l,(int)(Math.random()*(r-l+1))+l);
		Comparable v=arr[l];
		int j=l;
		for(int i=l+1;i<=r;i++){
			if(arr[i].compareTo(v)<0 )
			{
				j ++; 
				swap(arr, j, i);								
			}
		}
		swap(arr,l,j);
		return j;
	}
	public static void sort(Comparable[] arr,int l,int r){
		if(r-l<=15){
			InsertionSort.sort(arr, l, r);
			return;
		}
			
		int p=partition(arr,l,r);
		sort(arr,l,p-1);
		sort(arr,p+1,r);
				
	}
	public static void sort(Comparable[] arr){
		int n=arr.length;
		sort(arr,0,n-1);
		
	}
	public static  void swap(Comparable[] arr,int i,int j){
					Comparable t=arr[i];
					arr[i]=arr[j];
					arr[j]=t;
	}
	public static void main(String[] args) {
		 Comparable[] arr={1,5,6,84,15,26,355,26,35,36,45,-5,36,45,18,4,44,58};
		 QuickSort qs=new QuickSort();
		 qs.sort(arr);
		 for(Comparable e:arr){
			 System.out.print(e+" ");
			         }
		 System.out.println();
		 
	}

}
